LOJ528 求和

$\sum_{i=1}^n\sum_{j=1}^m \mu^2(\gcd(i,j))$

$\sum_{d=1}^{\min(n,m)}\mu^2(d)\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d]$

$\sum_{d=1}^{\min(n,m)}\mu^2(d) \sum_{t=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(t) \lfloor \frac{n}{td} \rfloor \lfloor \frac{m}{td} \rfloor$

$\sum_{T=1}^{\min(n,m)}\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d|T} \mu^2(d) \mu(\frac{T}{d})$

令 $\displaystyle f(n)=\sum_{d|n}\mu^2(d)\mu(\frac{T}{d})$

不难发现质数有以下取值：

$f(p^k)=\begin{cases} 1 & k = 0 \\ 0 & k = 1 ~~ or ~~ k \ge3 \\ -1 & k = 2 \end{cases}$

所以可以得到：

$f(n)=\begin{cases} \mu(\sqrt n) & n \text{ is a square number}\\ 0 & \text{otherwise} \end{cases}$

整除分块即可。

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long

const int MAXN = 4e6 , Mod = 998244353;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }

int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , Sumf[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
    mu[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) { prime[ ++ prnum ] = i; mu[ i ] = -1; }
        for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            if( i % prime[ j ] == 0 ) break;
            mu[ i * prime[ j ] ] = -mu[ i ];
        }
    }
    for( int i = 1 ; i <= MAXN ; i ++ ) Sumf[ i ] = Sumf[ i - 1 ] + mu[ i ];
}

int SumF( LL l , LL r ) {
    return ( Sumf[ (int)sqrt( r ) ] - Sumf[ (int)sqrt( l - 1 ) ] + Mod ) % Mod;
}
int Solve( LL n , LL m ) {
    int Ans = 0;
    for( LL l = 1 , r ; l <= min( n , m ) ; l = r + 1 ) {
        r = min( n / ( n / l ) , m / ( m / l ) );
        Ans = Add( Ans , Mul( Mul( n / l % Mod , m / l % Mod ) , SumF( l , r ) ) );
    }
    return Ans;
}

LL n , m;
int main( ) {
    sieve();
    scanf("%lld %lld",&n,&m);
    printf("%d\n", Solve( n , m ) );
    return 0;
}